package com.guchenbo.example.ds.tree;

/**
 * Created by CreGu on 2016/5/26.
 */
public class Tree {
    private Node root;

    /**
     * 不变性：插入肯定是在最末尾
     *
     * @param data
     */
    public void insert(int data) {
        Node node = new Node(data);
        if (root == null) {
            root = node;
        } else {
            Node current = root;
            Node parent;

            while (true) {
                parent = current;

                if (current.getData() > data) {
                    current = current.getLeftChild();
                    if (current == null) {
                        parent.setLeftChild(node);
                        return;
                    }
                } else {
                    current = current.getRigthChild();
                    if (current == null) {
                        parent.setRigthChild(node);
                        return;
                    }
                }
            }
        }
    }

    public Node find(int data) {
        Node current = root;
        while (current.getData() != data) {

            if (current.getData() > data) {
                current = current.getLeftChild();
            } else {
                current = current.getRigthChild();
            }

            if (current == null) {
                return current;
            }
        }
        return current;
    }

    public Node findMin() {
        Node current = root;
        Node parent;

        while (true) {
            parent = current;
            current = current.getLeftChild();
            if (current == null) {
                return parent;
            }
        }
    }

    public Node findMax() {
        Node current = root;
        Node parent;

        while (true) {
            parent = current;
            current = current.getRigthChild();
            if (current == null) {
                return parent;
            }
        }
    }

    /**
     * 如果找到要删除的节点，分为三种情况：
     * 1、删除的节点是叶节点，没有子节点（最简单）
     * 2、删除的节点有一个子节点
     * 3、删除的节点有两个子节点（最复杂）
     *
     * @param data
     * @return
     */
    public Node delete(int data) {
        Node delete;
//        找到要删除的node
        Node current = root;
        Node parent = null;
        boolean isLeftChild = true;

        while (current.getData() != data) {
            parent = current;
            if (data < current.getData()) {
                current = current.getLeftChild();
            } else {
                current = current.getRigthChild();
                isLeftChild = false;
            }
            if (current == null) {
//                not found node
                return null;
            }
        }

//        found,current is to delete
        if (current.getLeftChild() == null && current.getRigthChild() == null) {
//            第一种情况，节点没有子节点
            if (current == root) {
                root = null;

            } else if (isLeftChild) {
                parent.setLeftChild(null);
            } else {
                parent.setRigthChild(null);
            }

        } else if (current.getLeftChild() != null && current.getRigthChild() != null) {
//            第三种情况，有两个子节点
//            这种情况，需要找到删除节点的后继节点，后继节点是比删除的节点此高的节点
            Node successor = getSuccessor(current);

            if (isLeftChild) {
                parent.setLeftChild(successor);
            } else {
                parent.setRigthChild(successor);
            }

            successor.setLeftChild(current.getLeftChild());
        } else {
//            第二种情况，有一个子节点
            if (current.getLeftChild() != null) {

                if (current == root) {
                    root = current.getLeftChild();
                } else if (isLeftChild) {
                    parent.setLeftChild(current.getLeftChild());
                } else {
                    parent.setRigthChild(current.getLeftChild());
                }
            } else {

                if (current == root) {
                    root = current.getRigthChild();
                } else if (isLeftChild) {
                    parent.setLeftChild(current.getRigthChild());
                } else {
                    parent.setRigthChild(current.getRigthChild());
                }
            }
        }

        return current;
    }

    /**
     * 找到当前节点的后继节点
     *
     * @param current
     * @return
     */
    private Node getSuccessor(Node current) {
        Node right = current.getRigthChild();
        if (right.getLeftChild() == null) {
            return right;
        } else {
            Node leftChild = right.getLeftChild();
            Node successor = leftChild;
            Node parent = successor;

            while (leftChild != null) {
                parent = successor;
                successor = leftChild;
                leftChild = leftChild.getLeftChild();
            }

            parent.setLeftChild(successor.getRigthChild());
            successor.setRigthChild(right);
            return successor;
        }
    }

    public void inOrder(Node node) {
        if (node == null) {
            return;
        }

        inOrder(node.getLeftChild());
        node.display();
        inOrder(node.getRigthChild());
    }

    public void preOrder(Node node) {
        if (node == null) {
            return;
        }

        node.display();
        preOrder(node.getLeftChild());
        preOrder(node.getRigthChild());
    }

    public void postOrder(Node node) {
        if (node == null) {
            return;
        }

        postOrder(node.getLeftChild());
        postOrder(node.getRigthChild());
        node.display();
    }

    public Node getRoot() {
        return root;
    }

    public void setRoot(Node root) {
        this.root = root;
    }
}
